package com.moyoutian.leetcode;

/**
 * 1588. 所有奇数长度子数组的和
 * <p>
 * 给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
 * <p>
 * 子数组 定义为原数组中的一个连续子序列。
 * <p>
 * 请你返回 arr 中 所有奇数长度子数组的和 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [1,4,2,5,3]
 * 输出：58
 * 解释：所有奇数长度子数组和它们的和为：
 * [1] = 1
 * [4] = 4
 * [2] = 2
 * [5] = 5
 * [3] = 3
 * [1,4,2] = 7
 * [4,2,5] = 11
 * [2,5,3] = 10
 * [1,4,2,5,3] = 15
 * 我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
 * <p>
 * 示例 2：
 * <p>
 * 输入：arr = [1,2]
 * 输出：3
 * 解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。
 * <p>
 * 示例 3：
 * <p>
 * 输入：arr = [10,11,12]
 * 输出：66
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= arr.length <= 100
 * 1 <= arr[i] <= 1000
 */

public class Demo1588 {
    public static void main(String[] args) {
        int[] arr = new int[]{1};
        System.out.println(sumOddLengthSubarrays(arr));
    }

    public static int sumOddLengthSubarrays1(int[] arr) {
        if (arr == null) {
            return 0;
        }
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            //i左边的元素个数
            int left = i;
            //i右边的元素个数
            int right = arr.length - left - 1;
            //左边的偶数数量,+1是0个数也要算到偶数里 比如 [1,2,3] 选下标0为为i 那么左边0个数 右边1个数，加上i一共三个数满足基数要求，所以0个数也算一种可能。
            int left_even = (left >> 1) + 1;
            //右边的偶数数量
            int right_even = (right >> 1) + 1;
            //左边的奇数数量，0+奇数+奇数=偶数不满足所以不用+1
            int left_odd = (left + 1) >> 1;
            //右边的奇数数量
            int right_odd = (right + 1) >> 1;
            int count = left_even * right_even + left_odd * right_odd;

            sum += count * arr[i];
        }
        return sum;
    }

    public static int sumOddLengthSubarrays(int[] arr) {
        if (arr == null) {
            return 0;
        }
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += (((i >> 1) + 1) * (((arr.length - i - 1) >> 1) + 1) + ((i + 1) >> 1) * (((arr.length - i - 1) + 1) >> 1)) * arr[i];
        }
        return sum;
    }

}
